今天是紀錄LeetCode解題的第十天
來看前十題當中的第二題困難題

第十題題目：Given an input string s and a pattern p, implement regular expression matching with support for ' . ' and ' * ' where:

• ' . ' Matches any single character.
• ' * ' Matches zero or more of the preceding element.

The matching should cover the entire input string (not partial).
給定一個字串s和欲匹配字串p，完成正則表達式匹配，其中' . '匹配任意字元，' * '匹配零個或多個前一字元
字串應完全匹配，不是部分匹配

動態規劃(Dynamic Programming)

動態規劃是一種把大問題拆解成小問題來解的方法，且把已經算過的小問題結果紀錄下來，避免重複計算
簡單來說，動態規劃 = 把大問題拆成小問題 → 記住小問題結果 → 用小問題結果算大問題

動態規劃入門題-費波那契數列(Fibonacci Numbers)

我們先來了解動態規劃的概念，以最簡單的費波那契數列為例
題目：求第ｎ個費波那契數
我們知道費波那契數列的第0個和第1個元素分別為0、1，而第ｎ個費波那契數等於前兩個數相加(第n-1、n-2個數)

程式碼如下

def fib(n):
    if n <= 1:
        return n
    dp = [0] * (n + 1)
    dp[0],dp[1] = 0,1
    for i in range(2,n + 1)
        dp[i] = dp[i-1] + dp[i-2]
    return dp[n]
    
print(fib(10)) #55

這題是DP入門題，因為只需要記住目前狀態等於前兩個狀態的和

動態規劃解爬樓梯(Climbing Stairs)

題目：爬ｎ階樓梯，每次只能爬一階或兩階，有多少種不同的方法可以爬到ｎ階
假設ｎ=3，表示要爬到第三階，那麼方法就有1+1+1、1+2、2+1共三種方法，這題跟費波那契數列是一樣的概念，只是意義不同，爬到第三階的方法等於爬到第一階(1)+第二階(方法有1+1、2)的方法數，也就是說第n階=n-1階+n-2階的方法數

程式碼如下

def climbStairs(n):
    if n <= 2:
        return n
    dp = [0] * (n + 1)
    dp[1], dp[2] = 1, 2
    for i in range(3, n + 1):
        dp[i] = dp[i-1] + dp[i-2]
    return dp[n]

print(climbStairs(3))  #3
print(climbStairs(5))  #8

大概了解動態規劃是怎麼樣把問題細分的，我們回到LeetCode第十題

思路概念

1. 首先定義dp[i][j] = s[：i] 是否能匹配p[：j]（表示s的前i個字母是否能和p的前j個字母匹配）
2. 如果p[j-1] (當前字母)是一般字母或' . '則dp[i][j] = dp[i-1][j-1] 且 (s[i-1] == p[j-1] 或 p[j-1] == ' . ')，也就是說當前字母是匹配的，所以我們要看前一個字母的匹配狀態(看dp[i-1][j-1]的狀態)，換句話說，「目前能不能匹配」取決於「前面能不能匹配」
3. 如果p[j-1] = ' * '：
   (1)當成「零次」出現：dp[i][j] = dp[i][j-2]
   舉例：s='a', p='ab*'
   這裡的'b*'出現0次，p其實就等於a，所以我們要看dp[i][j-2]，也就是把'b*'拿掉，只看剩餘的'a'是否能匹配s
   (2)如果s[i-1] == p[j-2] (s的當前字母和p的前一個字母相等)，當成「多次」出現：dp[i][j] = dp[i-1][j]
   舉例：s='aa', p='a*'
   最後的' * '可以匹配第二個'a'
   那就看'a'(s[:1])能不能匹配'a*'(p[:2])
   簡單來說就是不斷的往前比對s字串，確認a*可以匹配到多少個a

程式碼

class Solution:
    def isMatch(self, s: str, p: str) -> bool:
        m,n = len(s),len(p)
        dp = [[False] * (n+1) for _ in range(m+1)]
        dp[0][0] = True #空字串匹配空的p

        #當s是空字串(i = 0)的時候，如果p的當前位置是*，那麼 p[:j] 可以等於「把前一個字母和*一起刪掉」，         所以就看dp[0][j-2]（即p去掉任意字母和*之後，能不能匹配空字串）
        for j in range(2,n+1):
            if p[j-1] == "*":
                dp[0][j] = dp[0][j-2]

        for i in range(1,m+1):
            for j in range(1,n+1):
                if p[j-1] == "." or p[j-1] == s[i-1]: #如果目前是.(任意字元)或字母相同代表匹配成功
                    dp[i][j] = dp[i-1][j-1] #設置成和前一個字元的匹配結果相同
                elif p[j-1] == "*":
                    dp[i][j] = dp[i][j-2] #視為零次
                    if p[j-2] == "." or p[j-2] == s[i-1]: #如果前一個字元是.或和目前字元相同
                        dp[i][j] = dp[i][j] or dp[i-1][j] #視為多次，只要零次或多次其中一個匹配就等於匹配成功
        return dp[m][n]

DP表格

我們來看這個表格代表什麼意思
在這個表格當中，當i=0、j=0時，表示s=' '、p=' ',所以兩者匹配
i=0、j=2：表示' '要去匹配'c*'(因為c可以匹配零個或多個，所以為True）
i=2、j=3：表示'aa'要去匹配'c(星號)a（這裡的a只能匹配一個a，但s有兩個a所以不能匹配為False）

執行過程

i=1（s[0] = 'a'）

• j=1 (p[0]='c') → 'a' != 'c' → False
• j=2 (p[1]='*') → 不符合前一字元是'a'，當作 0 次 → dp[1][2] = dp[1][0] = False
• j=3 (p[2]='a') → 匹配 → dp[1][3] = dp[0][2] = True (a匹配a)
• j=4 (p[3]='') → a 可以匹配 "a" → dp[1][4] = dp[1][2] or dp[0][4] = False or True = True
• j=5 (p[4]='b') → 'a' != 'b' → False
• 結果：[False, False, True, True, False]

i=2（s[1] = 'a'）

• j=1 (p[0]='c')→ 'a' != 'c' → False
• j=2 (p[1]='*')→ 不符合前一字元是'a'，當作 0 次 → dp[2][2] = dp[2][0] = False
• j=3 (p[2]='a')→ 'a' == 'a' → dp[2][3] = dp[1][2] = False (因為a不匹配aa)
• j=4 (p[3]='')→ 'a'匹配'aa' → dp[2][4] = dp[2][2] or dp[1][4] = False or True = True
• j=5 (p[4]='b')→ 'a' != 'b' → False
• 結果：[False, False, False, True, False]

i=3（s[2] = 'b'）

• j=1 (p[0]='c')→ 'b' != 'c' → False
• j=2 (p[1]='*')→ 不符合前一字元是'a'，當作 0 次 → dp[3][2] = dp[3][0] = False
• j=3 (p[2]='a')→ 'b' != 'a' → False
• j=4 (p[3]='')→ 'aab'不匹配'c(星號)a*' → dp[3][4] = dp[3][2] = False
• j=5 (p[4]='b')→ 'b' == 'b' → dp[3][5] = dp[2][4] = True
• 結果：[False, False, False, False, True]

總結

這題的關鍵在於動態規劃 (DP)，把「字串前綴是否能匹配」拆成小問題：
dp[i][j] = True 代表 s 的前 i 個字元 與 p 的前 j 個字元可以匹配
還有需要注意的點是' * '的兩種可能性，它可以是「沒有出現」，也可以代表「連續出現多次」，因此在DP表格裡會同時考慮「左兩格」與「上面一格」，並用 or 連接
最後，這題也可以充分了解到DP表格不是機械公式，而是把規則一步步轉換成邏輯關係的過程